package 图论;

import java.util.*;

public class FiveM28练习Dijkstra {
	public static int[] h, e, ne, w, dis;
	public static boolean[] st;
	public static int n, m;
	public static int idx = 0;
	
	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		h = new int[n + 10];
		e = new int[n + 10];
		ne = new int[n + 10];
		w = new int[n + 10];
		st = new boolean[n + 10];
		dis = new int [n + 10];
		
		//初始化
		Arrays.fill(dis, 0x3f3f3f3f);
		Arrays.fill(st, false);
		Arrays.fill(h,  -1);
		
		for(int i = 1; i <= m; i ++ ) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int z = sc.nextInt();
			add(x, y, z);
			add(y, x, z);
		}
		Dijkstra();
		
		for(int i = 1; i <= n; i ++ ) {
			System.out.print(i + "离起点1的距离：" + dis[i] + "\n");
		}
	}

	public static void add(int x, int y, int z) {
		e[idx] = y;
		ne[idx] = h[x];
		w[idx] = z;
		h[x] = idx ++ ;
	}
	
	public static void Dijkstra() {
		var q = new PriorityQueue<MyPair>();
		
		dis[1] = 0;
		q.add(new MyPair(1, 0));
		
		while(!q.isEmpty()) {
			var t = q.poll();
			System.out.print("pos = " + t.pos + "\n");
			int pos = t.pos;
			int val = t.val;
			for(int i = h[pos]; i != -1; i = ne[i]) {
				int j = e[i];
				if(dis[j] > val + w[i]) {
					dis[j] = val + w[i];
					q.add(new MyPair(j, dis[j]));
				}
			}
		}
	}
}

class MyPair implements Comparable<MyPair>{
	int pos;
	int val;
	
	public MyPair() {
		
	}
	public MyPair(int pos, int val) {
		this.pos = pos;
		this.val = val;
	}
	
	@Override
	public int compareTo(MyPair o) {
		return this.val - o.val;
	}
	
}